package cn.pugle.oj.leetcode;

import cn.pugle.oj.catalog.DaiBi;
import cn.pugle.oj.catalog.Unknown;

import java.util.Arrays;

/**
 * 错误的设计，不能求出结果
 * Created by tzp on 15-10-10.
 */
public class LC4_MedianOfTwoSortedArrays implements DaiBi {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int begin1 = 0, end1 = nums1.length - 1;
        int begin2 = 0, end2 = nums2.length - 1;
        return findMedianSortArraysR(nums1, begin1, end1, nums2, begin2, end2);
    }

    /**
     * 递归的查找两个有序数组的中位数
     *
     * @param nums1  数组1
     * @param begin1 开始索引(包括在内)
     * @param end1   结束索引(包括在内)
     * @param nums2  数组2
     * @return 中位数值
     */
    private final double findMedianSortArraysR(int[] nums1, int begin1, int end1, int[] nums2, int begin2, int end2) {
        if (begin1 == end1 && begin2 == end2) {
            return (nums1[begin1] + nums2[begin2]) / 2.0;
        }
        //下面可以有一点优化就是判断当其中某一个数组长度为1时，各项值就不用费力求了
        //数组中间两个数(偶数)的索引（奇数时，两者同）
        int left1 = begin1 + (end1 - begin1) / 2;
        int right1 = begin1 + (end1 - begin1 + 1) / 2;
        int left2 = begin2 + (end2 - begin2) / 2;
        int right2 = begin2 + (end2 - begin2 + 1) / 2;

        //最终求得的中位数，一定在两个数组中位数值的范围之间，以此递归缩短两个数组
        int medianValue1, medianValue2;//数组中位数值(小数问题 取>=的最小整数,这个数求insertPos与用实际的小数值是一样的) 137
        if ((nums1[left1] + nums1[right1]) % 2 == 0) {
            medianValue1 = (nums1[left1] + nums1[right1]) / 2;
        } else {
            medianValue1 = (nums1[left1] + nums1[right1] + 1) / 2;
        }
        if ((nums2[left2] + nums2[right2]) % 2 == 0) {
            medianValue2 = (nums2[left2] + nums2[right2]) / 2;
        } else {
            medianValue2 = (nums2[left2] + nums2[right2] + 1);
        }
        int insertPos1 = Arrays.binarySearch(nums1, begin1, end1 + 1, medianValue2);//数组2的中位数在数组1中的位置
        insertPos1 = insertPos1 >= 0 ? insertPos1 : -insertPos1 - 1;
        int insertPos2 = Arrays.binarySearch(nums2, begin2, end2 + 1, medianValue1);//数组1的中位数在数组2中的位置
        insertPos2 = insertPos2 >= 0 ? insertPos2 : -insertPos2 - 1;

        int newBegin1, newEnd1, newBegin2, newEnd2;
        if (insertPos1 >= right1) {
            newBegin1 = left1;
            newEnd1 = insertPos1 - 1;
        } else {
            newBegin1 = insertPos1 + 1;
            newEnd1 = right1;
        }
        if (insertPos2 >= right2) {
            newBegin2 = left2;
            newEnd2 = insertPos2 - 1;
        } else {
            newBegin2 = insertPos2 + 1;
            newEnd2 = right2;
        }
        return findMedianSortArraysR(nums1, newBegin1, newEnd1, nums2, newBegin2, newEnd2);
    }

    public static void main(String[] args) {
        int[] nums1 = new int[]{0, 1, 3, 6, 7, 9};
        int[] nums2 = new int[]{1, 2, 3, 4, 5};
//        System.out.println(Arrays.binarySearch(nums1, 0, 3, 10));
//        System.out.println(-Arrays.binarySearch(nums1, 0, 1, 10) - 1);
        double result = new LC4_MedianOfTwoSortedArrays().findMedianSortedArrays(nums1, nums2);
        System.out.println(result);
//        System.out.println(3 / 2);
    }
}
